package two.chapter_4.c4_1;

/**
 * 深入优先搜索
 */
public class DepthFirstSearch implements Search {
    private Graph g;
    private int count;
    private boolean[] marked;
    public DepthFirstSearch(Graph g, int s){
        this.g=g;
        marked=new boolean[g.v()];
        dfs(g,s);
    }

    private void dfs(Graph g, int v) {
        marked[v]=true;
        count++;
        for (Integer w:g.adj(v)){
            if (!marked[w])dfs(g,w);
        }
    }

    /**
     * 测试v和s是否连通
     * @param v
     * @return
     */
    public boolean marked(int v){
        return marked[v];
    }

    /**
     * 与s连通的顶点总数
     * @return
     */
    public int count(){
        return count;
    }
}
